Tree-structured data representations are pervasive. Because of their long history and many different forms and uses, there are a large variety of “trees” that appear superficially alike, or that have similar names, even though they are quite different in detail and use.
Therefore, a “bi-tree,” as defined herein, is a spatial partitioning of an N-dimensional space into a hierarchy of cells. A root cell, enclosing the N-dimensional space, is conditionally partitioned into 2N equally sized child cells along its mid-planes. Each child cell is then successively and conditionally partitioned in a similar manner.
Each cell of the bi-tree has associated characteristics comprising application specific data such as graphical elements, e.g., triangles, of a graphical object, e.g., a three-dimensional triangle mesh. Child cells in the bi-tree are indexed directly from their parent cell. Bi-trees can be fully populated, or sparse. In fully populated bi-trees, each cell is partitioned down to a deepest common level; in sparse bi-trees only selected cells are partitioned to reduce storage requirements.
FIG. 1 shows an example bi-tree 100 as defined herein. Although the example bi-tree 100 is a quadtree, i.e., a two-dimensional bi-tree, the method according to the invention can be extended to octrees, i.e., three-dimensional bi-trees, as well as lower and higher dimensional bi-trees because our method treats each dimension independently.
Cells branch from a root cell 101, through intermediate cells 102, to leaf cells 103. Typically, the cells are associated with application specific data and characteristics, e.g., a cell type for region quadtrees, or object indices for point quadtrees. The child cells are indexed 110 directly from their parent cell. Direct indexing can be done by ordering the child cells or pointers to the child cells in a memory.
A depth of the bi-tree 100 is NLEVELS. The level of the root cell 101 is LEVELROOT=NLEVELS−1. The level of a smallest possible cell is zero. The bi-tree 100 is defined over a normalized space [0, 1]×[0, 1]. Similarly, an N-dimensional bi-tree is defined over [0, 1]N. Although this may seem restrictive, in practice most spatial data can be represented in this normalized space by applying transformations to the coordinates of the data.
Quadtrees and octrees are used in many diverse fields such as computer vision, robotics, and pattern recognition. In computer graphics, quadtrees and octrees are used extensively for storing spatial data representing 2D images and 3D objects, see Samet, “The Quadtree and Related Hierarchical Data Structures,” Computing Surveys, Vol. 16, No. 2, pp. 187-260, June 1984, and Martin et al., “Quadtrees, Transforms and Image Coding,” Computer Graphics Forum, Vol. 10, No. 2, pp. 91-96, June 1991.
As shown in FIG. 2, quadtrees successively partition a region of space into four equally sized quadrants, i.e., cells. Starting from a root cell, cells are successively subdivided into smaller cells under certain conditions, such as when the cell contains an object boundary (region quadtree), or when the cell contains more than a specified number of objects (point quadtree). Compared to methods that do not partition space or that partition space uniformly, quadtrees and octrees can reduce the amount of memory required to store the data and improve execution times for querying and processing the data, e.g., collision detection and rendering.
Managing information stored in a bi-tree generally requires three basic operations: point location, region location, and neighbor searches.
Point location finds a leaf cell 201 containing a given point 200. For example, a quadtree that stores geographical data, such as city locations, is partitioned according to geographical coordinates, i.e., longitude and latitude. Point location can be used to find cities near a given geographical coordinate, i.e., the point 200.
Region location finds a smallest cell or set of cells that encloses a specified rectangular region 210 represented by a minimum vertex v0 211 and a maximum vertex v1 212. With the geographical quadtree example, region location can be used to determine all the cities that are within a given range of specified geographical coordinates.
A neighbor search finds a cell, in a specified direction, that is adjacent to a given cell. In the geographical quadtree, point location can be combined with neighbor searching to first locate a cell containing a given city and then to find nearby cities in a given direction. In all of these operations, the bi-tree is traversed by following pointers connecting the cells.
A fourth operation, called ray tracing, is used by graphics applications to render three-dimensional models on a display, see Foley et al., “Computer Graphics Principles and Practice,” Addison-Wesley, 1992. In these applications, graphical elements comprising a scene are placed in leaf cells of an octree. Ray tracing requires a sequential identification of leaf cells along a ray. One method for identifying these leaf cells combines point location and neighbor searching.
Traditional point location operations in a bi-tree require a downward branching through the bi-tree beginning at the root node. Branching decisions are made by comparing each coordinate of a point's position to a mid-plane position of a current enclosing cell.
Traditional neighbor searching in a bi-tree requires a recursive upward branching from a given cell to a smallest common ancestor of the given cell and a neighboring cell, and then a recursive downward branching to locate the neighbor. Each branch in the recursion relies on comparing values that depend on the current cell and its parent. Typically, the values are stored in tables.
Prior art point location, region location, and neighbor searching are time consuming because Boolean operations, i.e., comparisons, are used. Boolean operations are typically implemented by predictive branching logic in modern CPUs. Predictive branching will stall the instruction pipeline on incorrectly predicted branch instructions, see Knuth, The Art of Computer Programming, Volume 1, Addison-Wesley, 1998, and Knuth, MMIXware: A RISC Computer for the Third Millennium, Springer-Verlag, 1999.
Mispredictions occur frequently for traditional tree traversal operations because previous branch decisions generally have no relevance to future branch decisions, see Pritchard, “Direct Access Quadtree Lookup,” Game Programming Gems 2, ed. DeLoura, Charles River Media, Hingham, Mass., 2001.
In addition, traditional neighbor searching methods are recursive. Recursion increases overhead as a result of maintaining stack frames and making function calls. Also, prior art neighbor searching methods use table lookups which require costly memory accesses in typical applications. Finally, prior art neighbor searching methods are limited only to quadtrees and octrees and it is exceedingly complex to extend these methods to higher dimensional bi-trees.
FIG. 3 shows a typical prior art point location operation 300. The operation begins with a position of a given point 301 and a starting cell 302. First, characteristics (C) 303 associated with the cell 302 are tested 310. If true (T), then the cell 302 is a target cell 309 containing the point 301. If false (F), then each coordinate of the position of the point 301 is compared 320 to a corresponding mid-plane position of the cell 302. The comparisons 320 allow one to compute 330 an index to a next (child) cell 304 to be tested.
As stated above, the comparisons 320 require Boolean operations. For an N-dimensional bi-tree, at least N such Boolean operations are required for each cell visited during the traversal of the bi-tree. As stated above, these Boolean operations are likely to stall the instruction pipeline thereby degrading performance.
Pritchard, in “Direct Access Quadtree Lookup,” describes a region location operation for quadtrees that uses locational codes of the x and y boundaries of the bounding box of a region. Pritchards's quadtree is not a bi-tree under the above definition, because his child cells cannot be indexed directly from a parent cell.
That method operates on a hierarchy of regular arrays of cells, where each level is fully subdivided and contains four times as many cells as a previous level. His two-dimensional representation of spatial data requires a significant amount of memory, and would require even more memory for three- and higher-dimensional spatial data. Hence, that method is impractical for many applications.
Pritchard's method has two steps. First, that method uses locational codes of the left and right x boundaries and the top and bottom y boundaries of a region bounding box to determine a level of an enclosing cell. Then a scaled version of a position of a bottom-left vertex of the region bounding box is used to index into a regular array at this level.
Traditionally, locational codes have been used with “linear quadtrees” and “linear octrees”, see H. Samet, “Applications of Spatial Data Structures: Computer Graphics, Image Processing, GIS,” Addison-Wesley, Reading, Mass., 1990. Linear quadtrees and linear octrees are not bi-trees under our definition. Rather, linear quadtrees and linear octrees are comprised of a list of leaf cells where each leaf cell contains its interleaved locational code and other cell specific data. In general, linear quadtrees and linear octrees are more compact than bi-trees, e.g., they do not represent intermediate cells and they do not provide explicit links for direct indexing, at the expense of more costly and complicated processing methods.
Locational codes for linear quadtrees and linear octrees interleave bits that comprise coordinate values of a cell's minimum vertex such that linear quadtrees use locational codes of base 4 (or 5 if a “don't care” directional code is used) and linear octrees use locational codes of base 8 (or 9), see H. Samet, “Applications of Spatial Data Structures: Computer Graphics, Image Processing, GIS,” Addison-Wesley, Reading, Mass., 1990.
In computer graphics and volume rendering, ray tracing methods often make use of octrees to accelerate tracing rays through large empty regions of space. Those methods determine non-empty leaf cells along a ray passing through the octree and then process ray-surface intersections within these cells.
There are two basic approaches for tracing a ray through an octree: bottom-up and top-down. Bottom-up methods start at the first leaf cell encountered by the ray and then use neighbor finding techniques to find each subsequent leaf cell along the ray. Top-down methods start from the root cell and use a recursive procedure to find offspring leaf cells that intersect the ray. An extensive summary of methods for traversing octrees during ray-tracing is described by Havran, “A Summary of Octree Ray Traversal Algorithms,” Ray Tracing News, 12(2), pp. 11-23, 1999.
Stolte and Caubet, in “Discrete Ray-Tracing of Huge Voxel Spaces,” Computer Graphics Forum, 14(3), pp. 383-394, 1995, describe a top-down ray tracing approach that uses locational codes for voxel data sets stored in an octree. They first locate a leaf cell containing a point where a ray enters the octree. Then, for each leaf cell without a ray-surface intersection, a 3D DDA is used to incrementally step along the ray, in increments proportional to a size of a smallest possible leaf cell, until a boundary between the leaf cell and a neighboring next cell is encountered. The neighboring next cell is then found by popping cells from a recursion stack to locate a common ancestor of the leaf cell and the neighboring next cell and then traversing down the octree using their point location method. However, their method requires Boolean comparisons and thus suffers from the misprediction problems described above.
Therefore, it is desired to provide a traversal method for N-dimensional bi-trees that improves performance over the prior art by avoiding Boolean operations and eliminating recursion and memory accesses for table lookup, without increasing memory requirements.